﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Runtime.Serialization;
using System.ComponentModel.Composition;

using NuMetaheuristics.Genotypes;
using NuMetaheuristics.Operators.Vector;
using NuMetaheuristics.Operators.Value;
using NuMetaheuristics.Utility;

namespace NuMetaheuristics.Contexts
{
    /// <summary>
    /// Used to find solutions to knapsack problems (0-1, bounded, and 
    /// unbounded). The integer vector represents the quantity of each item to 
    /// be put in the knapsack. Bigger fitness is better. Candidates are 
    /// awarded higher fitness for a higher total value, and penalized for 
    /// having a total weight which is above or below the target.
    /// </summary>
    public class Knapsack : IContext<IntegerVectorGenotype>, IDeserializationCallback
    {
        /// <summary>
        /// The number of different item types that could be put into the 
        /// knapsack.
        /// </summary>
        [DataMember]
        private int _slots;

        /// <summary>
        /// Initialize knapsack vectors.
        /// </summary>
        [DataMember]
        private IntegerVectorInitializer _initializer;

        /// <summary>
        /// The actual values to associate with each item type.
        /// </summary>
        [DataMember]
        private DoubleVectorGenotype _values;

        /// <summary>
        /// The actual weights to associate with each item type.
        /// </summary>
        [DataMember]
        private DoubleVectorGenotype _weights;

        /// <summary>
        /// The most of each item type that can be put into a knapsack slot.
        /// </summary>
        [DataMember]
        private int _maxItemsPerSlot;

        /// <summary>
        /// The maximum value possible to associate with an item type. 
        /// The actual value is randomly selected for each item type.
        /// </summary>
        [DataMember]
        private double _maxValuePerItem;

        /// <summary>
        /// The maximum weight possible to associate with an item type. 
        /// The actual weight is randomly selected for each item type.
        /// </summary>        
        [DataMember]
        private double _maxWeightPerItem;

        /// <summary>
        /// The maximum total weight allowed from all of the items in the 
        /// knapsack.
        /// </summary>
        [DataMember]
        private double _maxTotalWeight;

        private RandomNumberGenerator _rng;

        /// <summary>
        /// The default, no-argument constructor.
        /// </summary>
        public Knapsack()
        {
            _rng = new RandomNumberGenerator();
        }

        /// <summary>
        /// The complete constructor, which initializes all properties.
        /// </summary>
        public Knapsack(int slots, int maxItemsPerSlot, double maxValuePerItem, double maxWeightPerItem, double maxTotalWeight)
        {
            _slots = slots;
            _maxItemsPerSlot = maxItemsPerSlot;
            _maxValuePerItem = maxValuePerItem;
            _maxWeightPerItem = maxWeightPerItem;
            _maxTotalWeight = maxTotalWeight;
            
            _initializer = new IntegerVectorInitializer(new IntegerRandomInitializer(0, maxItemsPerSlot + 1));

            var values = new DoubleVectorGenotype(slots);
            var valuesInitializer = new DoubleVectorInitializer(new DoubleRandomInitializer(0.0, maxValuePerItem));
            valuesInitializer.Operate(ref values);
            _values = values;

            var weights = new DoubleVectorGenotype(slots);
            var weightsInitializer = new DoubleVectorInitializer(new DoubleRandomInitializer(0.0, maxWeightPerItem));
            weightsInitializer.Operate(ref weights);
            _weights = weights;

            _rng = new RandomNumberGenerator();
        }

        /// <summary>
        /// The complete constructor, which initializes all properties, and additionally
        /// sets <c>Weights</c> and <c>Values</c> with the given vectors.
        /// </summary>
        public Knapsack(int slots, int maxItemsPerSlot, DoubleVectorGenotype values, DoubleVectorGenotype weights, double maxTotalWeight)
        {
            _slots = slots;
            _maxItemsPerSlot = maxItemsPerSlot;
            _maxValuePerItem = values.Vector.Max();
            _maxWeightPerItem = weights.Vector.Max();
            _maxTotalWeight = maxTotalWeight;

            _initializer = new IntegerVectorInitializer(new IntegerRandomInitializer(0, maxItemsPerSlot + 1));

            _values = values;
            _weights = weights;

            _rng = new RandomNumberGenerator();
        }

        public IntegerVectorGenotype Produce(bool initialize, bool makeValid, bool evaluate)
        {
            var candidate = new IntegerVectorGenotype(_slots);

            if (initialize)
            {
                Initialize(ref candidate);
            }

            if (makeValid && !IsValid(candidate))
            {
                MakeValid(ref candidate);
            }

            if (evaluate)
            {
                Evaluate(ref candidate);
            }

            return candidate;
        }

        public void Initialize(ref IntegerVectorGenotype candidate)
        {
            _initializer.Operate(ref candidate);
        }

        public void Evaluate(ref IntegerVectorGenotype candidate)
        {
            double totalWeight = 0.0;
            double totalValue = 0.0;
            double score = 0.0;

            for(int i = 0; i < candidate.Vector.Length; i++)
            {
                double numItemsInSlot = (double)candidate.Vector[i];
                double weightPerItem = _weights.Vector[i];
                double valuePerItem = _values.Vector[i];

                double slotValue = numItemsInSlot * valuePerItem;
                double slotWeight = numItemsInSlot * weightPerItem;

                totalValue += slotValue; 
                totalWeight += slotWeight;
            }

            score = totalValue;

            ////total value accounts for part of the score, and is relative
            ////to the maximum possible value per item.
            //score += (totalValue / MaxValuePerItem);

            if (totalWeight > _maxTotalWeight)
            {
                score /= (2.0 * (double)_maxItemsPerSlot);
            }

            ////total weight accounts for part of the score, and is relative
            ////to the maximum allowed total weight.
            //double weightDiff = Math.Abs(totalWeight - MaxTotalWeight);
            //score -= (weightDiff / MaxWeightPerItem);

            //if (score < 0.0)
            //    score = 0.0;

            candidate.Fitness = new FitnessBiggerIsBetter(score);
        }

        public bool IsValid(IntegerVectorGenotype candidate)
        {
            double totalWeight = 0.0;

            for (int i = 0; i < candidate.Vector.Length; i++)
            {
                double numItemsInSlot = (double)candidate.Vector[i];
                double weightPerItem = _weights.Vector[i];
                double slotWeight = numItemsInSlot * weightPerItem;
                totalWeight += slotWeight;
            }

            return (totalWeight <= _maxTotalWeight);
        }

        public void MakeValid(ref IntegerVectorGenotype candidate)
        {
            if (IsValid(candidate))
                return;

            var original = (int[])candidate.Vector.Clone();
            var modified = new int[candidate.Vector.Length];

            double totalWeight = 0.0;
            bool weightLimitReached = false;

            while (!weightLimitReached)
            {
                int index = _rng.Next(0, original.Length);

                if (original[index] > 0)
                {
                    double itemWeight = _weights.Vector[index];

                    if ((itemWeight + totalWeight) > _maxTotalWeight)
                    {
                        weightLimitReached = true;
                    }
                    else
                    {
                        original[index]--;
                        modified[index]++;
                        totalWeight += itemWeight;
                    }
                }
            }

            modified.CopyTo(candidate.Vector, 0);
        }

        public void OnDeserialization(object sender)
        {
            _rng = new RandomNumberGenerator();
        }
    }
}
